package 剑指offer;

import common.ListNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;


/** 2.链表*/
public class day2_06_24_35 {

    /**===========================================================================================================================
     * 剑指 Offer 06. 从尾到头打印链表
     * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     * 1、先计算出链表长度，再在数组中从后向前放入数组
     * 2、直接将链表元素从头到尾放入栈中，再从栈中取出到数组中
     * */
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack=new Stack<>();
        while (head!=null){
            stack.push(head.val);
            head=head.next;
        }
        int[] res=new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i]=stack.pop();
        }
        return res;
    }


    /**===========================================================================================================================
     * 剑指 Offer 24. 反转链表
     * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     * 1.栈，先进后出
     * 2.双链表
     * 3.迭代：在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用
     * 4.递归：
     * */
    public ListNode reverseList1(ListNode head) {
        if (head==null) return null;
        Stack<ListNode> stack=new Stack<>();
        while (head!=null){
            stack.push(head);
            head=head.next;
        }
        ListNode resRoot=stack.pop();
        ListNode t=resRoot;
        while (!stack.isEmpty()){
            t.next=stack.pop();
            t=t.next;
        }
        //最后一个节点的next为null，否则会有环
        t.next=null;
        return resRoot;
    }
    public ListNode reverseList2(ListNode head) {
        //用一个新的链表记录
        ListNode newList=null;
        while (head!=null){
            ListNode next = head.next;
            head.next=newList;
            newList=head;
            head=next;
        }
        return newList;
    }
    public ListNode reverseList3(ListNode head) {
        if (head==null) return null;
        ListNode proNode=null;
        while (head!=null){
            ListNode nextNode=head.next;
            head.next=proNode;
            proNode=head;
            head=nextNode;
        }
        return proNode;
    }
    //reverseList4返回将链表反转后的头节点
    public ListNode reverseList4(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode newHead=reverseList4(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }


    /**===========================================================================================================================
     * 剑指 Offer 35. 复杂链表的复制
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     * 1、递归+map记录
     * 2、迭代：首先将该链表中每一个节点拆分为两个相连的节点，对于任意一个原节点 S，其拷贝节点 S'即为其后继节点。这样，我们可以直接找到每一个拷贝节点 S'的随机指针应当指向的节点，
     * 即为其原节点 S的随机指针指向的节点 T的后继节点 T'。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。
     * 当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。
     * */
    Map<Node,Node> cachedNdoe=new HashMap<>();
    public Node copyRandomList1(Node head) {
        if (head==null) return null;
        if (!cachedNdoe.containsKey(head)){
            Node headNew=new Node(head.val);
            cachedNdoe.put(head,headNew);
            //当head还没有处理过时，递归拷贝他的next和random即可
            headNew.next=copyRandomList1(head.next);
            headNew.random=copyRandomList1(head.random);
        }
        return cachedNdoe.get(head);
    }

    public Node copyRandomList(Node head) {
        if (head==null) return null;
        Node node=head;
        //先遍历链表给每个节点后添加一个新节点
        while (node!=null){
            Node newNode=new Node(node.val);
            newNode.next=node.next;
            node.next=newNode;
            node=node.next.next;
        }
        node=head;
        //将每个节点的random节点复制
        while (node!=null){
            Node newNode=node.next;
            //此时新节点的random应该时原节点randow节点的下一个
            newNode.random=(node.random==null)? null:node.random.next;
            node=node.next.next;
        }
        Node headNew=head.next;
        //拆分去除原节点，剩下的就是新复制的
        node=head;
        while (node!=null){
            Node newNode=node.next;
            node.next=node.next.next;
            newNode.next=(newNode.next==null)?null:newNode.next.next;
            node=node.next;
        }
        return headNew;
    }
}
